template<typename _Ty>
struct SkipList {
	int n;
	int cnt;
	int maxh;
	std::vector<_Ty> key;
	std::vector<int> key_count;
	std::vector<int> level;
	std::vector<std::vector<int>> len;
	std::vector<std::vector<int>> next_node;

	SkipList() {}

	SkipList(int n) {
		init(n);
	}

	void init(int n) {
		this->n = n;
		maxh = std::__lg(n) + 1;
		cnt = 1;
		key.resize(n + 1, 0);
		key_count.resize(n + 1, 0);
		level.resize(n + 1, 0);
		len.resize(n + 1);
		for (auto& x : len) {
			x.resize(maxh + 1, 0);
		}

		next_node.resize(n + 1);
		for (auto& x : next_node) {
			x.resize(maxh + 1, 0);
		}

		key[cnt] = std::numeric_limits<_Ty>::min();
		level[cnt] = maxh;
	}

	int randLexel() {
		int ans = 1;
		while ((std::rand() / double(RAND_MAX)) < 0.5) {
			ans++;
		}

		return std::min(ans, maxh);
	}

	int find(int i, int h, _Ty num) {
		while (next_node[i][h] != 0 && key[next_node[i][h]] < num) {
			i = next_node[i][h];
		}

		if (h == 1) {
			if (next_node[i][h] != 0 && key[next_node[i][h]] == num) {
				return next_node[i][h];
			}
			else {
				return 0;
			}
		}

		return find(i, h - 1, num);
	}

	void addCount(int i, int h, _Ty num) {
		while (next_node[i][h] != 0 && key[next_node[i][h]] < num) {
			i = next_node[i][h];
		}
		if (h == 1) {
			key_count[next_node[i][h]]++;
		}
		else {
			addCount(i, h - 1, num);
		}
		len[i][h]++;
	}

	int addNode(int i, int h, int j) {
		int rightCount = 0;
		while (next_node[i][h] != 0 && key[next_node[i][h]] < key[j]) {
			rightCount += len[i][h];
			i = next_node[i][h];
		}

		if (h == 1) {
			next_node[j][h] = next_node[i][h];
			next_node[i][h] = j;
			len[j][h] = key_count[next_node[j][h]];
			len[i][h] = key_count[next_node[i][h]];
			return rightCount;
		}
		else {
			int downCount = addNode(i, h - 1, j);
			if (h > level[j]) {
				len[i][h]++;
			}
			else {
				next_node[j][h] = next_node[i][h];
				next_node[i][h] = j;
				len[j][h] = len[i][h] + 1 - downCount - key_count[j];
				len[i][h] = downCount + key_count[j];
			}
			return rightCount + downCount;
		}
	}

	void add(_Ty num) {
		if (find(1, maxh, num) != 0) {
			addCount(1, maxh, num);
		}
		else {
			key[++cnt] = num;
			key_count[cnt] = 1;
			level[cnt] = randLexel();
			addNode(1, maxh, cnt);
		}
	}

	void removeCount(int i, int h, _Ty num) {
		while (next_node[i][h] != 0 && key[next_node[i][h]] < num) {
			i = next_node[i][h];
		}

		if (h == 1) {
			key_count[next_node[i][h]]--;
		}
		else {
			removeCount(i, h - 1, num);
		}
		len[i][h]--;
	}

	void removeNode(int i, int h, int j) {

		if (h < 1) {
			return;
		}


		while (next_node[i][h] != 0 && key[next_node[i][h]] < key[j]) {
			i = next_node[i][h];
		}

		if (h > level[j]) {
			len[i][h]--;
		}
		else {
			next_node[i][h] = next_node[j][h];
			len[i][h] += len[j][h] - 1;
		}
		return removeNode(i, h - 1, j);
	}


	void remove(_Ty num) {
		int node = find(1, maxh, num);
		if (node != 0) {
			if (key_count[node] > 1) {
				removeCount(1, maxh, num);
			}
			else {
				removeNode(1, maxh, node);
			}
		}
	}


	// 当前在i号节点的h层，查询有多少个数字比num小
	int samll(int i, int h, _Ty num) {
		int rightCount = 0;
		while (next_node[i][h] != 0 && key[next_node[i][h]] < num) {
			rightCount += len[i][h];
			i = next_node[i][h];
		}
		if (h == 1) {
			return rightCount;
		}
		else {
			return rightCount + samll(i, h - 1, num);
		}
	}


	// 查询 num 的排名
	int getRank(_Ty num) {
		return samll(1, maxh, num) + 1;
	}

	// 查询排名第 x 的值
	_Ty getIndex(int x) {
		return getIndex(1, maxh, x);
	}

	_Ty getIndex(int i, int h, int x) {
		int c = 0;
		while (next_node[i][h] != 0 && c + len[i][h] < x) {
			c += len[i][h];
			i = next_node[i][h];
		}

		if (h == 1) {
			return key[next_node[i][h]];
		}
		else {
			return getIndex(i, h - 1, x - c);
		}
	}

	// 查询 num 的前驱
	_Ty getPre(_Ty num) {
		return getPre(1, maxh, num);
	}

	_Ty getPre(int i, int h, _Ty num) {
		while (next_node[i][h] != 0 && key[next_node[i][h]] < num) {
			i = next_node[i][h];
		}

		if (h == 1) {
			return i == 1 ? std::numeric_limits<_Ty>::min() : key[i];
		}
		else {
			return getPre(i, h - 1, num);
		}
	}

	// 查询 num 的后继
	_Ty getPost(_Ty num) {
		return getPost(1, maxh, num);
	}

	_Ty getPost(int i, int h, _Ty num) {
		while (next_node[i][h] != 0 && key[next_node[i][h]] < num) {
			i = next_node[i][h];
		}

		if (h == 1) {
			if (next_node[i][h] == 0) {
				return std::numeric_limits<_Ty>::max();
			}
			if (key[next_node[i][h]] > num) {
				return key[next_node[i][h]];
			}
			i = next_node[i][h];
			if (next_node[i][h] == 0) {
				return std::numeric_limits<_Ty>::max();
			}
			else {
				return key[next_node[i][h]];
			}
		}
		else {
			return getPost(i, h - 1, num);
		}
	}
};